package demo.practice.leetcode_eveyday;

import java.util.Stack;

public class P628 {

    public static void main(String[] args) {
        P628 p628= new P628();
        p628.maximumProduct(new int[]{-1,-2,-3});
    }


    public int maximumProduct(int[] nums) {
        if(nums==null|| nums.length<3)
            return 0;
        Stack<Integer> stack = new Stack<>();

        for (int num : nums) {
            //单调栈，从大到小的顺序。然后如果栈size>3 弹出栈顶的
            pushSort(stack, num);
            if (stack.size() > 3)
                stack.pop();
        }

        return stack.pop()*stack.pop()*stack.pop();
    }


    private void pushSort( Stack<Integer> stack,int num ){
        if (stack.empty()) {
            stack.push(num);
            return;
        }
        if(stack.peek()<num){
            int top = stack.pop();
            pushSort(stack,num);
            stack.push(top);
        }else{
            stack.push(num);
        }
    }
}
